This description relates to accelerated decompression.
The DEFLATE algorithm is an efficient lossless data compression algorithm which utilizes a combination of the LZ77 algorithm and Huffman encoding (DEFLATE Compressed Data Format Specification version 1.3, Deutsch et al., Network Working Group RFC 1951, May 1996, “RFC-1951”). In DEFLATE compression, a file is divided into a sequence of data blocks and each data block is compressed separately. An end-of-block symbol is used to denote the end of each block. The LZ77 algorithm contributes to DEFLATE compression by allowing repeated character patterns to be represented with (length, distance) symbol pairs where a length symbol represents the length of a repeating character pattern and a distance symbol represents its distance, in bytes, to an earlier occurrence of the pattern. If a character pattern is not represented as a repetition of its earlier occurrence, it is represented by a sequence of literal symbols corresponding to 8-bit byte patterns.
Referring to FIG. 1, Huffman encoding is used in DEFLATE compression for encoding length, distance, literal, and end-of-block symbols. The literal symbols (values from 0 to 255), used for representing all 8-bit byte patterns, together with the end-of-block symbol (the value 256) and the length symbols (values 257 to 285), are encoded as literal/length codes using a first Huffman code tree. The distance symbols (represented by the values from 0 to 29) are encoded as distance codes using a separate, second, Huffman code tree. Every length symbol has two associated values, a base length value and an additional value denoting the number of extra bits to be read from the input bit-stream. The extra bits read are an integer, which is added to the base length value to give the absolute length represented by the length symbol occurrence. Likewise, every distance symbol has two associated values, a base distance value and an additional value denoting the number of extra bits to be read from the input bit-stream. The base distance value added to the integer made up of the associated number of extra bits from the input bit-stream gives the absolute distance represented by the distance symbol occurrence.
Thus, the compressed block is a hybrid of encoded literals and LZ77 look-back indicators terminated by an end-of-block indicator. As RFC-1951 explains:                encoded data blocks in the “deflate” format consist of sequences of symbols drawn from three conceptually distinct alphabets: either literal bytes, from the alphabet of byte values (0.255), or <length, backward distance> pairs, where the length is drawn from (3.258) and the distance is drawn from (1 . . . 32, 768). In fact, the literal and length alphabets are merged into a single alphabet (0 . . . 285), where values 0 . . . 255 represent literal bytes, the value 256 indicates end-of-block, and values 257 . . . 285 represent length codes (possibly in conjunction with extra bits following the symbol code) . . .                    (Paragraph 3.2.5)                        